708E - Student's Camp - CodeForces Solution

#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=100100,M=2020,P=1e9+7;
int n,m,x,y,K,sum,ans,s0,s1,s2,s3;
int iv[N],fc[N],vf[N],w[N],f[M][M];
int qpw(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%P)if(y&1) z=1ll*z*x%P;return z;}
int C(int x,int y){return 1ll*fc[x]*vf[x-y]%P*vf[y]%P;}
int main(){
	scanf("%d%d%d%d%d",&n,&m,&x,&y,&K);
    x=1ll*x*qpw(y,P-2)%P;
    fc[0]=vf[0]=iv[1]=1;
	FOR(i,2,K) iv[i]=1ll*(P-P/i)*iv[P%i]%P;
	FOR(i,1,K) fc[i]=1ll*fc[i-1]*i%P,vf[i]=1ll*vf[i-1]*iv[i]%P;
    FOR(i,0,K) w[i]=1ll*qpw(x,i)*qpw(P+1-x,K-i)%P*C(K,i)%P;
    f[0][m]=1;
    FOR(i,1,n){
		s0=f[i-1][m];s1=w[0];s2=s3=0;
		FOR(j,1,m){
			f[i][j]=(1ll*s0*s1%P-s3+P)%P*w[m-j]%P;
			(s0+=f[i-1][m-j])%=P;
			(s1+=w[j])%=P;
			(s2+=f[i-1][j])%=P;
			(s3+=1ll*w[j]*s2%P)%=P;
		}
	}
    FOR(i,1,m) (ans+=f[n][i])%=P;
	cout<<ans<<'\n';
}/*1692611903.8041084*/